package leetcode_500;

/**
 * ArrangingCoins_441 用硬币堆楼梯 要保证每层的硬币数和楼层一样 返回哪一层不是完整的楼层
 * 2018年8月18日 下午1:38:51
 * @author 周杨
 * describe :
 *
 */
public class ArrangingCoins_441 {

	
	 /**
	 * 2018年8月18日 下午1:42:35
	 * @author 周杨
	 * describe :正当解 每次递减硬币数 AC 8%
	 */
	public int arrangeCoins(int n) {
	        int res=1;
	        while(n>=0){
	        	if(n>=res){
	        		n-=res;
	        		res++;
	        	}
	        	else
	        		return res-1;
	        }
	        return -1;
	 }
	
	 //T(n) = n+(Tn-1) = (1+n)n/2;
    /**
     * 2018年8月18日 下午1:43:09
     * @author 周杨
     * describe :用二分查找 每次都用总数计算方式是否匹配 AC 100%
     */
    public int arrangeCoins1(int n) {
        //find maximum (1+k)k/2 <=n, reurn k
        if(n == 0) return 0;
        long left = 1;
        long right = n;
        while(left + 1 < right)
        {
            long mid = left + (right - left) / 2;
            long count = (mid + 1) * mid / 2; // use * use long
            if(count <= n)
            {
                left = mid;
            }
            else
            {
                right = mid;
            }
        }
        return (int)left;
    }
}
